namespace Test.ConsoleProgram.Algorithm.Solution
{
    [TestDescription("算法: 0410. 分割数组的最大值")]
    public class No0410_SplitArray : AbsBaseTestItem
    {
        /*
        给定一个非负整数数组和一个整数 m，你需要将这个数组分成 m 个非空的连续子数组。设计一个算法使得这 m 个子数组各自和的最大值最小。
        注意:
        数组长度 n 满足以下条件:
            1 ≤ n ≤ 1000
            1 ≤ m ≤ min(50, n)

        示例:

            输入:
            nums = [7,2,5,10,8]
            m = 2

            输出:
            18

            解释:
            一共有四种方法将nums分割为2个子数组。
            其中最好的方式是将其分为[7,2,5] 和 [10,8]，
            因为此时这两个子数组各自的和的最大值为18，在所有情况中最小。
        */

        public override void OnTest()
        {
            Assert.TestExe(SplitArray, new int[] { 7, 2, 5, 10, 8 }, 2, 18);
        }

        /// <summary>
        ///  方法二：二分查找 + 贪心
        /// </summary>
        public int SplitArray(int[] nums, int m)
        {
            int left = 0, right = 0;
            for (int i = 0; i < nums.Length; i++)
            {
                int item = nums[i];
                right += item;
                if (left < item)
                {
                    left = item;
                }
            }
            bool Check(int[] nums, int x, int m)
            {
                int sum = 0, cut = 1;
                for (int i = 0; i < nums.Length; i++)
                {
                    int item = nums[i];
                    if (sum + item > x)
                    {
                        cut++;
                        sum = item;
                    }
                    else
                    {
                        sum += item;
                    }
                }
                return cut <= m;
            };
            while (left < right)
            {
                int mid = (right - left) / 2 + left;
                if (Check(nums, mid, m))
                {
                    right = mid;
                }
                else
                {
                    left = mid + 1;
                }
            }
            return left;
        }
    }
}
